package sort;
/**
 * 插入排序算法
 * @author Heng
 * 
 */
public class insertionSort {
	public static void main(String[] args){
		int[] array = {7,6,8,0,15,23,2,3,5};
		
		insertionSort(array);

		for(int i = 0; i < array.length; i++){
			System.out.println(array[i]);
		}
	}
	/**
	 * 工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
	 * @param array
	 */
	private static void insertionSort(int[] array){
		for(int i = 1; i < array.length; i++){
			// 记录未排序的数组的第一个
			int currentValue = array[i];
			// 记录未排序的数据的头一个
			int  index = i;
			for(int j = i-1; j > -1; j--){
				if(array[j] <= currentValue){
					break;
				}else{
					int temp = array[j];
					array[j] = currentValue;
					array[index] = temp;
					index--;
				}
			}
		}
	}
}
